package bst;

/**
 * @program: play-structure
 * @author: baichen
 * 二分搜索树，需要有可比性(节点数据类型相同)，所以要继承Comparable
 **/
public class BST<E extends Comparable<E>> {
    //声明对应的节点类型
    private class Node {
        public E e;
        public Node left, right;

        //构造函数，左右孩子初始化
        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    private Node root;      //根结点
    private int size;       //size 记录当前二叉树存储元素的数量

    public BST() {
        root = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {    //二分搜索树为空
        return size == 0;
    }

    // 向二分搜索树中添加新的元素e
    public void add(E e) {
        if (root == null) {
            root = new Node(e);
            size++;
        } else {
            add(root, e);
        }
    }

    // 向以node为根的二分搜索树中插入元素e，递归算法
    private void add(Node node, E e) {    //传入参数 Node 与 e
        if (e.equals(node.e)) {  //【递归的终止条件】传入的e已经存在于树中
            return;
        }
        //插入的e比Node节点中的e小，插入左子树中,这里要注意因为不是基本类型，所以要用compareTo方法，不能直接用<
        else if (e.compareTo(node.e) < 0 && node.left == null) {
            node.left = new Node(e);    //左子树为空，直接让node的左孩子为新插入的e
            size++;
            return;
        } else if (e.compareTo(node.e) > 0 && node.right == null) {
            node.right = new Node(e);
            size++;
            return;
        }
        //递归调用，插入的e比Node节点中的e小，e插入左子树
        if (e.compareTo(node.e)<0){
            add(node.left,e);
        }else {
            add(node.right,e);
        }
    }
}
